package org.niu.listnode;

import java.util.*;

public class SortInList {
    public ListNode sortInList (ListNode head) {
        // write code here
        PriorityQueue<ListNode> q = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });
        while (head!=null){
            q.offer(head);
            head = head.next;
        }
        ListNode ans = new ListNode(-1);
        ListNode tail = ans;
        while(!q.isEmpty()){
            ListNode h = q.poll();
            tail.next = h;
            tail = tail.next;
        }
        tail.next = null;
        return ans.next;
    }
}
